// https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/

// 算法思路总结：
// 1. 双栈实现最小栈结构
// 2. 主栈存储所有元素，辅助栈存储历史最小值
// 3. 入栈时比较并更新最小值栈
// 4. 出栈时同步维护最小值栈状态
// 5. 时间复杂度：O(1)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <stack>
#include <algorithm>

class MinStack 
{
public:
    stack<int> _min;
    stack<int> _elem;

    MinStack() 
    {}
    
    void push(int x) 
    {
        _elem.push(x);
        if (_min.empty() || _min.top() >= _elem.top())
        {
            _min.push(x);
        }
    }
    
    void pop() 
    {
        if (_min.top() == _elem.top())
        {
            _min.pop();
        }
        _elem.pop();
    }
    
    int top() 
    {
        return _elem.top();
    }
    
    int getMin() 
    {
        return _min.top();
    }
};

int main()
{
    MinStack* minStack = new MinStack();

    minStack->push(-2);
    minStack->push(0);
    minStack->push(-3);

    cout << minStack->getMin() << endl;   

    minStack->pop();

    cout << minStack->top() << endl;     
    cout << minStack->getMin() << endl;   

    return 0;
}